Regular map (graph theory)

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold such as a sphere, torus, or Klein bottle into topological disks, such that every flag (an incident vertex-edge-face triple) can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

Contents

Overview

Regular maps are typically defined and studied in three ways: topologically, group-theoretically, and graph-theoretically.

Topological approach

Topologically, a map is a 2-cell decomposition of a closed compact 2-manifold.

The genus g, of a map M is given by Euler's relation \chi (M) = |V| - |E| %2B|F| which is equal to 2 -2g if the map is orientable, and 2 - g if the map is non-orientable. It is a crucial fact that there is a finite (non-zero) number of regular maps for every orientable genus except the torus.

Group-theoretical approach

Group-theoretically, the permutation representation of a regular map M is a transitive permutation group C, on a set \Omega of flags, generated by a fixed-point free involutions r0, r1, r2 satisfying (r0r2)2= I. In this definition the faces are the orbit of F = <r0, r1>, edges are the orbit of E = <r0, r2>, and vertices are the orbit of V = <r1, r2>. More abstractly, the automorphism group of any regular map is the non-degenerate, homomorphic image of a <2,m,n>-triangle group.

Graph-theoretical approach

Graph-theoretically, a map is a cubic graph \Gamma with edges coloured blue, yellow, red such that: \Gamma is connected, every vertex is incident to one edge of each colour, and cycles of edges not coloured blue, have length 4. Note that \Gamma is the flag graph or graph encoded map (GEM) of the map, defined on the vertex set of flags \Omega and is not the skeleton G = (V,E) of the map. In general, |\Omega| = 4|E|.

A map M is regular iff Aut(M) acts regularly on the flags. Aut(M) of a regular map is transitive on the vertices, edges, and faces of M. A map M is said to be reflexible iff Aut(M) is regular and contains an automorphism \phi that fixes both a vertex v and a face f, but reverses the order of the edges. A map which is regular but not reflexible is said to be chiral.

Examples

The following is the complete determination of simple reflexible maps of positive Euler characteristic: the sphere and the projective plane (Coxeter 80).

Characteristic Genus Schläfli symbol Group Graph Notes
2 0 {p,2} C2 × Dihp Cp Dihedron
2 0 {2,p} C2 × Dihp p-fold K2 Hosohedron
2 0 {3,3} Sym4 K4 Tetrahedron
2 0 {4,3} C2 × Sym4 K2,2,2 Octahedron
2 0 {3,4} C2 × Sym4 K4 × K2 Cube
2 0 {5,3} C2 × Alt5 Dodecahedron
2 0 {3,5} C2 × Alt5 K6 × K2 Icosahedron
1 - {2p,2}/2 Dih2p Cp Hemidihedron
1 - {2,2p}/2 Dih2p p-fold K2 Hemihosohedron
1 - {4,3} Sym4 K4 Hemicube
1 - {4,3} Sym4 2-fold K3 Hemioctahedron
1 - {5,3} Alt5 Petersen graph Hemidodecahedron
1 - {3,5} Alt5 K6 Hemi-icosahedron

See also

References